// Sorting functions for comparing attributes in adobe::value_t
// Copyright 2005 (C) Ralph Thomas

#include <model/internal/sort.h>
#include <model/attributeNames.h>
#include <model/model.h>
#include <boost/cstdint.hpp>

namespace model {
	template<typename innerType> bool lessThan( const adobe::value_t& a,
		const adobe::value_t& b ) {
		//
		// If a can't be converted then we return false, if
		// b can't be converted then we return true. That
		// means that anything which can't be converted will
		// end up at one end of the sort.
		//
		innerType at, bt;
		if( !a.get<innerType>( at ) ) return false;
		if( !b.get<innerType>( bt ) ) return true;
		return at < bt;
	}
	sorter_t getSorter( const std::string& attr ) {
		if( attr == kName ) return (sorter_t)lessThan<std::string>;
		if( attr == kType ) return (sorter_t)lessThan<std::string>;
		if( attr == kModifiedDate ) return (sorter_t)lessThan<unsigned int>;
		if( attr == kFrom ) return (sorter_t)lessThan<std::string>;
		if( attr == kParent ) return (sorter_t)lessThan<std::string>;
		if( attr == kSize ) return (sorter_t)lessThan<boost::intmax_t>;
		if( attr.find( kExtAttrPrefix ) == 0 )
			return (sorter_t)lessThan<std::string>;
		return sorter_t( 0 );
	}
	class sorterImpl {
	  public:
		//
		/// The cacheEntry structure keeps a child, and keeps a cache
		/// of it's attribute which we sort on.
		//
		struct child_t {
			child_t( const std::string u ) : dirty( true ), url( u ) {}

			//
			// Because the value and the dirty flag both relate to a
			// cache that is built while the children are being sorted
			// they are mutable. It might be a better idea to iterate
			// over the list of children and update dirty children prior
			// to sorting, instead of doing everything in one loop.
			// 
			mutable adobe::value_t	val;	///< Cached value.
			mutable bool		dirty;	///< Is this cache entry dirty?
			std::string		url;	///< The URL of the model.
			//
			/// Operator to make us only bother checking the URL part
			/// for equality.
			///
			/// \param	u	the URL to check against.
			/// \return	true if we are equal, false otherwise.
			//
			bool operator==( const std::string& u ) {
				return (url == u);
			}
			//
			/// Get the value of the given attribute (in the most
			/// inefficient way!). This function is typically bound
			/// with the current attribute name in order to form a
			/// parameterless getter function.
			///
			/// \param	attr	the attribute to get.
			//
			void update( const std::string& attr ) const {
				if( !dirty ) return;
				model* m( model::fromString( url ) );
				if( !m ) return;
				val = m->getAttribute( attr );
				dirty = false;
				m->release();
			}
			//
			/// Return the value of a given child_t getting
			/// the attribute if required.
			///
			/// \param	attr	the name of the attribute
			/// \param	child	the child to get the value of.
			/// \return	the child's value.
			//
			static const adobe::value_t& getter( const std::string& attr,
				const child_t& child ) {
				if( !child.dirty ) return child.val;
				child.update( attr );
				return child.val;
			}
		};
		typedef std::vector<child_t> children_t;
		children_t	children;	///< All of the children.
		std::string	attribute;	///< The attribute to sort by.
		//
		// void removeChild( const std::string& url )
		//
		/// Remove the child with the given URL. If there is no child of
		/// the given URL then do nothing.
		///
		/// \param	url	the URL of the child to remove.
		//
		void removeChild( const std::string& url ) {
			children_t::iterator first( children.begin() );
			children_t::iterator last( children.end() );
			while( first != last ) {
				if( *first == url ) {
					children.erase( first );
					return;
				}
				first++;
			}
		}
		//
		// void markAllDirty()
		//
		/// Mark all children as dirty. This is only a good idea when the
		/// sorting attribute has changed.
		//
		void markAllDirty() {
			children_t::iterator first( children.begin() );
			children_t::iterator last( children.end() );
			while( first != last ) {
				first->dirty = true;
				first++;
			}
		}
		//
		// void markDirty( const std::string& url )
		//
		/// Mark a single child dirty, if it exists.
		//
		void markDirty( const std::string& url ) {
			children_t::iterator first( children.begin() );
			children_t::iterator last( children.end() );
			while( first != last ) {
				if( *first == url ) first->dirty = true;
				first++;
			}
		}
		//
		// void sort()
		//
		/// Perform a sort using the current sorter.
		//
		void sort() {
			//
			// Verify that we actually can sort!
			//
			if( attribute.empty() ) return;
			sorter_t s = getSorter( attribute );
			if( !s ) return;
			//
			// Use boost::bind to make a sorter function which can
			// fetch values for dirty children as it goes.
			//
			boost::function<const adobe::value_t& (const child_t&)> get =
				boost::bind( child_t::getter, attribute, _1 );
			//
			// Perform the sort, creating a new sorter function which
			// uses the "get" function created above to get the values
			// it sorts.
			//
			std::sort( children.begin(), children.end(),
				boost::bind( s, boost::bind( get, _1 ),
					boost::bind( get, _2 ) ) );
		}
		//
		// adobe::array_t getChildren() const
		// 
		/// Return a adobe::array_t the sorted children.
		//
		adobe::array_t getChildren() {
			adobe::array_t kids;
			//
			// Perform a sort before going any further. This will be
			// fast unless there are any dirty children.
			//
			sort();
			children_t::iterator first( children.begin() );
			children_t::iterator last( children.end() );
			while( first != last ) {
				kids.push_back( adobe::value_t( first->url ) );
				first++;
			}
			return kids;
		}
	};
	sorter::sorter() : _impl( new sorterImpl ) {}
	sorter::~sorter() {
		if( _impl ) delete _impl;
	}
	void sorter::addChild( const std::string& url ) {
		_impl->children.push_back( url );
	}
	void sorter::removeChild( const std::string& url ) {
		_impl->removeChild( url );
	}
	bool sorter::setSort( const std::string& attr ) {
		_impl->attribute = attr;
		_impl->markAllDirty();
		return true;	// XXX: fix!
	}
	const std::string& sorter::getSort() const {
		return _impl->attribute;
	}
	adobe::array_t sorter::getChildren() const {
		return _impl->getChildren();
	}
	void sorter::childNotify( const std::string& url, const std::string& attr ) {
		if( attr != _impl->attribute ) return;
		_impl->markDirty( url );
	}
};

